package com.googlecode.gaal.data.impl;

import java.util.AbstractQueue;
import java.util.Iterator;

/**
 * A priority queue with bounded capacity
 * 
 * @author akislev
 * 
 * @param <E>
 *            the type of the element
 */
public class BoundedPriorityQueue<E> extends AbstractQueue<E> {

    protected final Object[] queue;
    protected int size;

    /**
     * Creates a BoundedPriorityQueue with the given (fixed) capacity.
     */
    public BoundedPriorityQueue(int capacity) {
        queue = new Object[capacity];
    }

    @SuppressWarnings("unchecked")
    @Override
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        if (queue[0] == null) {
            size++;
        } else if (((Comparable<E>) e).compareTo((E) queue[0]) <= 0) {
            return false;
        }
        queue[0] = e;
        int k = 0;
        while (k < queue.length - 1) {
            int j = k + 1;
            if (queue[j] == null || ((Comparable<E>) queue[k]).compareTo((E) queue[j]) > 0) {
                Object tmp = queue[j];
                queue[j] = queue[k];
                queue[k] = tmp;
                k = j;
            } else {
                break;
            }
        }
        return true;
    }

    @Override
    public boolean add(E o) {
        return offer(o);
    }

    @SuppressWarnings("unchecked")
    @Override
    public E poll() {
        if (size == 0)
            return null;
        E result = (E) queue[queue.length - 1];
        int k = queue.length - 1;
        while (k > 0) {
            int j = k - 1;
            queue[k] = queue[j];
            k = j;
        }
        queue[0] = null;
        size--;
        return result;
    }

    @SuppressWarnings("unchecked")
    @Override
    public E peek() {
        if (size == 0)
            return null;
        return (E) queue[queue.length - 1];
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int i = 0;

            @Override
            public boolean hasNext() {
                return i < size;
            }

            @SuppressWarnings("unchecked")
            @Override
            public E next() {
                return (E) queue[queue.length - 1 - i++];
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

    @Override
    public int size() {
        return size;
    }
}
